package flashBack;

/**
 * @author zxc
 * @date 2023/01/17 16:04
 **/

import java.util.LinkedList;
import java.util.List;

/**
 * 题目 ：复原IP地址
 * 题目详述 ：
 * 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能从s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。
 * 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
 * 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
 */
public class RestoreIpAddresses {
    /**
     * 思路 ：
     * IP地址的特点 ：
     * （1）IP地址中某个分段seg的取值范围 ：[0 , 255];
     * （2）如果IP地址中某个分段seg不是0的话，而是其他数字的话，则该数组不能够以0开头;
     * @param s
     * @return
     */
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new LinkedList<>();
        /**
         * 参数分析 ：
         * （1）第一个参数str ：字符串s;
         * （2）第二个参数index ：正在遍历字符在字符串中的下标;
         * （3）第三个参数segI ：当前分段下标;
         * （与后面的seg相互对应，即当前分段下标所对应的seg）
         * （4）第四个参数seg ：当前分段下标segI所对应的字符串;
         * （5）第五个参数ip ：即，ip字段用来存储某个可能合理的ip;
         * （6）第六个参数result ：即，result集合用来存储所有可能的合理ip;
         */
        flushBack(s , 0 , 0 , "" , "" ,result);
        return result;
    }
    // 回溯法 ：求取合法的IP地址
    private void flushBack(String str, int index, int segI, String seg, String ip, List<String> result) {
        // 满足题目条件的IP地址，就将其加入到result集合中;
        /**
         * 所需要取满足的条件 ：
         * （1）index == str.length(),即代表了str字符串被遍历完;
         * （2）segI == 3,即代表了分段数量合乎IP地址的规范（IP地址被划分为4段）;
         * （3）isValid(seg)
         * 由于最后一个分段字符串seg未能够进行有效性检测 && 最后一个分段字符串seg是没有添加到ip地址的;
         * ===> 即，需要进行有效性检测 && 同时，在result集合中添加的ip地址（ip = ip + seg）;
         */
        if(index == str.length() && segI == 3 && isValid(seg)){
            result.add(ip + seg);
        }
        // 即，边界条件 ：index < str.length() && segI < 4
        // 即，当前遍历的字符需要小于/等于字符串str的长度 && IP地址的分段需要小于/等于4;
        /**
         * 问题 ：为何此处的ip参数在经过添加seg分段字符串操作之后不需要进行回退操作？
         * 原因 ：
         * （1）ip参数是在flushBack方法中递归传递的，所以每一层递归都对应了不同的ip参数
         * （简单来说，对于ip的修改操作只在内层递归有效，若是退出内层递归，在外层递归中ip地址仍然是未修改的ip地址;）
         * （2）即，只需要退出内层递归，所要使用的ip地址就会改为该外层递归的ip地址;
         */
        else if(index < str.length() && segI < 4){
            char ch = str.charAt(index);
            if(isValid(seg + ch)){ // 判断分段字符串seg在加上字符ch后，是否仍然有效;
                // 若是分段字符串是有效的话，则需要给分段字符串seg加上字符ch; 同时，遍历字符串str中的第index + 1个字符;
               flushBack(str , index + 1 , segI , seg + ch , ip , result);
            }
            // 此if语句是用来增加分段的，同时此分段是以字符ch开头的;
            /**
             * 思考 ：
             * （1）segI < 3这个限制条件，很好理解，就是根据IP地址的特性（IP地址只能够被划分为四个分段数字）
             * （2）seg.length() > 0这个限制条件，乍一看感觉可有可无的；
             * 一开始，笔者也是这样想的，当时在真正提交的时候，才发现出现了有分段字符串seg的长度 == 0的诡异现象;
             * 为啥子呢 ？
             * a.一开始，笔者是这样子想的 ：经过前面的有效性判断，seg分段字符串怎么可能为null;
             * 但是，笔者忘记了最重要的一点，回溯法会取遍历所有的情况;
             * ===》 即，最开始进入flushBack方法时，seg为null;
             * 若是不对于（seg是否为null）去进行限定的话，则seg == null时，其也是满足segI < 3的，所以会出现ip地址第一个分段为null的异常情况;
             */
            if(seg.length() > 0 && segI < 3){
                // 即，增加一个新的分段 && ip = ip + seg + "."（即，将前一个分段字符串添加到ip地址）
                // && seg = "" + ch（即，清空seg字段同时将ch字符加入到seg字段中，构成新的分段字符串）
                flushBack(str , index + 1 , segI + 1 , "" + ch , ip + seg + "." , result);
            }
        }

    }

    private boolean isValid(String childStr) {
        // 有效的判断条件 ：
        // （1）分段字符串的取值范围：[0 , 255];
        // （2）如果IP地址中某个分段seg不是0的话，而是其他数字的话，则该数组不能够以0开头;
        return Integer.valueOf(childStr) <= 255
                && (childStr.equals("0") || childStr.charAt(0) != '0');
        /**
         * 总结 ：
         * （1）str.charAt(index),即获取字符串str的第index个字符;
         * （2）Integer.valueOf(str),即将字符串str转化为Integer类型;
         */
    }
}
